package com.congee02;

import java.util.*;

public class MergeKLists {

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode sentinel = new ListNode(-1);
        ListNode p = sentinel;
        int minIndex;
        while ((minIndex = findMin(lists)) != -1) {
            p.next = lists[minIndex];
            lists[minIndex] = lists[minIndex].next;
            p = p.next;
        }

        return sentinel.next;
    }

    private int findMin(ListNode... nodes) {
        int ret = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nodes.length; i++) {
            ListNode node = nodes[i];
            if (node != null && node.val < min) {
                min = node.val;
                ret = i;
            }
        }
        return ret;
    }

}
